package lc;
import org.junit.*;
public class Lcp12 {
    class Solution {
        public int minTime(int[] time, int m) {
            /**
                寻找刷题最大耗时x，可以得到f(x)：刷题天数，单调递减函数
             */
             int lo = 0, //全都靠求助
             hi = 0; //一天之内靠自己完成所有题
             for (int t: time) {
                 hi += t;
             }
             while (lo < hi) {
                 int mid = (hi - lo) / 2 + lo;
                 int cnt = count(time, mid);
                 if (cnt > m) {
                     //刷題耗時不足
                     lo = mid + 1;
                 } else {
                     hi = mid;
              }
             }
    
             System.out.println(count(time, 3));
             return lo;
        }
        //t:当前规定每天最大耗时
        public int count(int[] nums, int t) {
            //为了最小化时间，记录每轮刷题最大耗时，利用求助减掉他
            int max = 0, cnt = 1, cur = 0;
            boolean used = false; //当天有咩有用掉求助
            for (int i = 0; i < nums.length; i++) {
                int n = nums[i];
                if (n + cur > t) {
                    if (!used) {
                        //用掉求助
                        used = true;
                        max = Math.max(max, n);
                        cur -= max;
                    } else {
                        //只能第二天再刷
                        cnt++;
                        cur = 0;
                        used = false;
                        max = 0;
                    }
                    i--;
                    continue;
                }
                max = Math.max(max, n);
                cur += n;
            }
            return cnt;
        }
    }

        @Test
        public void test() {
            Solution s = new Solution();
            int[] nums = new int[]{1,2,3,3};
            System.out.println(s.count(nums, 1));
            System.out.println(s.minTime(nums, 2));
        }
}
